package middle;

/**
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class PopulatingNextRightPointersInEachNodeII {
    /**
     * 用了两个Node指针将二叉树抽象成一个链表，真的太强了。
     * 参考官方题解
     * */
    class Solution {
        // 记录下一层的开始结点
        Node nextStart;
        // 链表的尾指针
        Node last;
        public Node connect(Node root) {
            Node startNode = root;
            while (startNode != null) {
                nextStart = null;
                last = null;
                // 先遍历当层
                for (Node pNode = startNode; pNode != null; pNode = pNode.next) {
                    if (pNode.left != null) {
                        handler(pNode.left);
                    }
                    if (pNode.right != null) {
                        handler(pNode.right);
                    }
                }
                // 连接下一层
                startNode = nextStart;
            }
            return root;
        }

        private void handler(Node pNode) {
            if (nextStart == null) {
                nextStart = pNode;
            }
            if (last != null) {
                last.next = pNode;
            }
            last = pNode;
        }
    }

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }
}
